"""
2447. 最大公因数等于 K 的子数组数目
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。



示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。


提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 109
"""
from math import gcd
from typing import List


class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        ans = 0
        for i in range(len(nums)):
            g = 0
            for j in range(i, len(nums)):
                g = gcd(g, nums[j])
                if g % k:
                    break
                if g == k:
                    ans += 1
        return ans

    #todo
    def subarrayGCD_res1(self, nums: List[int], k: int) -> int:
        ans = 0
        a = []  # [GCD，相同 GCD 区间的右端点]
        i0 = -1
        for i, x in enumerate(nums):
            if x % k:  # 保证后续求的 GCD 都是 k 的倍数
                a = []
                i0 = i
                continue
            a.append([x, i])
            # 原地去重，因为相同的 GCD 都相邻在一起
            j = 0
            for p in a:
                p[0] = gcd(p[0], x)
                if a[j][0] != p[0]:
                    j += 1
                    a[j] = p
                else:
                    a[j][1] = p[1]
            del a[j + 1:]
            if a[0][0] == k:  # a[0][0] >= k
                ans += a[0][1] - i0
        return ans

    def subarrayGCD_err1(self, nums: List[int], k: int) -> int:
        ar = []
        for i,j in enumerate(nums):
            if j % k == 0:
                ar.append(i)
        print(ar)
        ans = 0
        i = 1
        pre = 1
        preIndex = 0
        while i<len(ar):
            if ar[i] == ar[i-1] + 1 :
                pre = pre + (i - preIndex) + 1
            else:
                ans += pre
                pre = 1
                preIndex = i
            i+=1
        ans += pre

        return ans
if __name__ == '__main__':
    print(Solution().subarrayGCD_res1([9,3,3,1,2,9,6,3],3))